# 动态规划类：dp数组定义以及下标的含义；递推公式；dp数组如何初始化；遍历顺序；打印dp数组
class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 法一：空间复杂度为O(1）
        # if n == 0:
        #     return 0
        # elif n == 1:
        #     return 1
        # else:
        #     a, b = 0, 1
        #     for i in range(2, n+1):
        #         c = a + b
        #         a = b
        #         b = c
        #     return b
        # 法二：空间复杂度为O(n）
        if n == 0:
            return 0
        elif n == 1:
            return 1
        else:
            dp = [0] * (n+1)
            dp[0] = 0
            dp[1] = 1
            for i in range(2, n+1):
                dp[i] = dp[i-1] + dp[i-2]
            return dp[n]
if __name__ == '__main__':
    n = 4
    print(Solution().fib(n))
# 思路：
# 斐波那契数列的递推公式为：F(n) = F(n-1) + F(n-2)，其中F(0) = 0，F(1) = 1。
# 因此，我们可以用两个变量a和b，初始值a=0，b=1，然后用循环计算F(n)的值，并更新a和b的值，直到n为0或1。
# 时间复杂度：O(n)，因为循环执行了n次。 
# 空间复杂度：O(1)，因为只用了两个变量。